//
// Created by Administrator on 2021/6/15.
//

//给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，
//写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/binary-search
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int lhs = 0, rhs = (int) nums.size() - 1;
        while (lhs <= rhs) {
            int mid = lhs + (rhs - lhs) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                lhs = mid + 1;
            } else rhs = mid - 1;
        }
        return -1;
    }

    int search2(vector<int> &nums, int target) {
        auto pos = lower_bound(nums.begin(), nums.end(), target);
        if (pos==nums.end() or *pos!=target)
            return -1;
        else
            return pos - nums.begin();
    }
};

int main() {
    vector<int> nums{-1, 0, 3, 5, 9, 12};
    Solution sol;
    cout << sol.search2(nums, 9) << endl;
    return 0;
}